class Solution {
    private int[] disjointSet;
    private boolean hasCycle;
    private int count;
    public int[] findRedundantConnection(int[][] edges) {
        count = 0;
        hasCycle = false;
        for (int i = 0; i < edges.length; i++) {
            count = Math.max(edges[i][0], count);
            count = Math.max(edges[i][1], count);
        }
        disjointSet = new int[++count];
        for (int i = 0; i < count; i++) {
            disjointSet[i] = i;
        }
        for (int[] edge : edges) {
            int node1 = edge[0];
            int node2 = edge[1];
            unionSet(node1, node2);
            if (hasCycle) {
                return edge;
            }
        }
        return null;
    }
    private int find(int x) {
        if (disjointSet[x] == x) return x;
        return disjointSet[x] = find(disjointSet[x]);
    }
    private void unionSet(int x, int y) {
        x = find(x);
        y = find(y);
        if (x != y) {
            disjointSet[x] = y;
        } else {
            hasCycle = true;
        }
    }
    
}
